package com.zxy.leetcode._00000_00099._00040_00049;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/multiply-strings/
 *
 * 字符串相乘
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，
 * 返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *
 * 标签：乘法
 */
public class Test00043 {

    public static void main(String[] args) {
        Test00043 test = new Test00043();
        System.out.println(test.multiply("0", "123"));
        System.out.println(test.multiply("2", "3"));
        System.out.println(test.multiply("123", "456"));
    }

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        if (num1.equals("1")) {
            return num2;
        }
        if (num2.equals("1")) {
            return num1;
        }

        List<Integer> aList = new ArrayList<>(num1.length());
        List<Integer> bList = new ArrayList<>(num2.length());
        // 这里进行了翻转，最后面返回数据要翻转回来
        for (int i=num1.length()-1; i>=0; i--) {
            aList.add(num1.charAt(i) - '0');
        }
        for (int i=num2.length()-1; i>=0; i--) {
            bList.add(num2.charAt(i) - '0');
        }

        int capacity = num1.length() * num2.length() + 1;
        List<Integer> list = new ArrayList<>(capacity);
        // 这里先初始化0，后面要过滤0
        for (int i=0; i<capacity; i++) {
            list.add(0);
        }

        for (int i=0; i<aList.size(); i++) {
            int a = aList.get(i);
            int c = 0;  // 进位
            int index = i;
            for (int b : bList) {
                int m = a * b + c + list.get(index);
                list.set(index++, m % 10);
                if (m >= 10) {
                    c = m / 10;
                }else {
                    c = 0;
                }
            }
            if (c > 0) {
                list.set(index, c + list.get(index));
            }
        }

        int count0 = 0; // 尾部0的数量
        for (int i=list.size()-1; i>=0; i--) {
            if (list.get(i) == 0) {
                count0 ++;
            }else {
                break;
            }
        }

        StringBuilder stringBuilder = new StringBuilder(list.size()-count0);
        for (int i=list.size()-1-count0; i>=0; i--) {
            stringBuilder.append(list.get(i));
        }

        return stringBuilder.toString();
    }

}
